/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM38 在二叉树中找到两个节点的最近公共祖先
 * <a href="https://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116?tpId=295&tqId=1024325&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">...</a>
 * User: DELL
 * Data: 2022-12-31
 * Time: 22:13
 */

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}

public class Solution {
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        //当root为null时，即表示该分支上没有val等于o1或者o2的结点
        if (root == null) {
            return -1;
        }
        //当root的val等于o1或者o2的时候，即root为最近公共祖先
        if ((root.val == o1) || (root.val == o2)) {
            return root.val;
        }
        //递归
        int left = lowestCommonAncestor(root.left,o1,o2);
        int right = lowestCommonAncestor(root.right,o1,o2);
        //当两个结点均出现在root的左分支
        if (right == -1) {
            return left;
        }
        //当两个结点均出现在root的右分支
        if (left == -1) {
            return right;
        }
        //剩下即为两个结点分别出现在root的左右分支，即最近公共祖先为root
        return root.val;
    }
}